package my.algo.sort;

public class Quick {

    /**
     * 交换排序之快速排序：以表中第一个元素作为中心轴，比它小的都移动到它的左边，比它大的都移动到它的右边，左右分别递归以上操作。
     */
    public static void quick(int[] a) {
        quick(a, 0, a.length-1);
    }

    private static void quick(int[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int j = partition(a, lo, hi);
        print(a);
        quick(a, lo, j-1);
        quick(a, j+1, hi);
    }

    /**
     * 选择第一个元素作为轴，先从后往前遍历选择比第一个元素小的放到第一个元素所在位置。
     * 然后从前往后遍历选择比轴大的元素放到刚刚被交换到一个元素的元素所在的位置。
     * 以此类推，直到从前往后遍历的下标等于从后往前遍历的下标时，将第一个元素移动到该下标的位置。
     * 此时，该下标的左边都小于该元素，右边都大于该元素，返回该下标。
     */
    private static int partition(int[] a, int lo, int hi) {
        int v = a[lo];
        while (lo < hi) {
            while (lo < hi && a[hi] >= v) {
                hi--;
            }
            a[lo] = a[hi];
            while (lo < hi && a[lo] <= v) {
                lo++;
            }
            a[hi] = a[lo];
        }
        a[lo] = v;
        return lo;
    }

    private static void print(int[] a) {
        for (int i : a) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] arts) {
        int[] a = {50, 30, 60, 90, 40, 21, 54, 44, 32, 75, 46, 52};
        quick(a);
    }
}
